package oct2013;

import java.util.ArrayList;

public class TextJustification {
	public ArrayList<String> fullJustify(String[] words, int L) {
		ArrayList<String> res = new ArrayList<String>();
		int n = words.length;
		int i = 0;
		while (i < n) {
			int wlen = 0;
			int wnum = 0;
			int k = i;
			while (i < n && wlen + wnum + words[i].length() <= L) {
				wlen += words[i].length();
				wnum++;
				i++;
			}
			int space = L - wlen;
			StringBuilder sb = new StringBuilder();
			int cnt = 0;
			if (i == n) {
				while (k < i) {
					sb.append(words[k++]);
					if (space-- > 0)
						sb.append(' ');
				}
				while (space-- > 0)
					sb.append(' ');
			} else {
				while (k < i) {
					sb.append(words[k++]);
					if (wnum - 1 == 0) {
						for (int j = 0; j < space; ++j)
							sb.append(' ');
					} else if (k != i) {
						for (int j = 0; j < space / (wnum - 1); ++j)
							sb.append(' ');
						if (space % (wnum - 1) > cnt)
							sb.append(' ');
					}
					cnt++;
				}
			}
			res.add(sb.toString());
		}
		return res;
	}

}
